package org.liaohailong.helloworld.study;

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * Author: liaohailong
 * Time: 2021/4/29 09:16
 * Describe: 二叉树
 */
public class BTree {

    // 前序遍历 - 根，逐级左右
//    public List<Integer> preorderTraversal(TreeNode root) {
//        List<Integer> result = new LinkedList<>();
//        Stack<TreeNode> stack = new Stack<>();
//        while (root != null || !stack.isEmpty()) {
//            while (root != null) {
//                result.add(root.val);
//                stack.push(root);
//                root = root.left;
//            }
//            root = stack.pop().right;
//        }
//
//        return result;
//    }


    // 中序遍历 左 根 右 - 递归
//    public List<Integer> inorderTraversal(TreeNode root) {
//        List<Integer> res = new LinkedList<>();
//        traversal(root,res);
//        return res;
//    }
//
//    private void traversal(TreeNode root,List<Integer> res){
//        if (root != null) {
//            traversal(root.left,res);
//            res.add(root.val);// 最左
//            traversal(root.right,res);
//        }
//    }

    // 中序遍历 左 根 右 - 非递归
//    public List<Integer> inorderTraversal(TreeNode root) {
//        List<Integer> result = new LinkedList<>();
//        Stack<TreeNode> stack = new Stack<>();
//
//        while (root != null || !stack.isEmpty()) {
//            while (root != null) {
//                stack.push(root);
//                root = root.left;
//            }
//            TreeNode lastLeft = stack.pop();
//            result.add(lastLeft.val);
//            root = lastLeft.right;
//        }
//
//        return result;
//    }


    // 后序遍历 左 右 根 - 递归
//    public List<Integer> postorderTraversal(TreeNode root) {
//        List<Integer> res = new LinkedList<>();
//        traversal(root, res);
//        return res;
//    }
//
//    private void traversal(TreeNode root, List<Integer> res) {
//        if (root != null) {
//            traversal(root.left, res);
//            traversal(root.right, res);
//            res.add(root.val);// 打印根
//        }
//    }

    // 后序遍历 左 右 根 - 非递归
//    public List<Integer> postorderTraversal(TreeNode root) {
//        LinkedList<Integer> result = new LinkedList<>();
//        if (root== null) return result;
//        Stack<TreeNode> stack = new Stack<>();
//
//        // 栈内容：根，左，右
//        stack.push(root);
//        while (!stack.isEmpty()) {
//            TreeNode node = stack.pop();
//            result.addFirst(node.val);
//
//            if (node.left != null) {
//                stack.push(node.left);
//            }
//            if (node.right != null) {
//                stack.push(node.right);
//            }
//        }
//        return result;
//    }

//    public List<List<Integer>> levelOrder(TreeNode root) {
//        List<List<Integer>> result = new ArrayList<>();
//        levelTraversal(root, result, 0);
//        return result;
//    }
//
//    private void levelTraversal(TreeNode node, List<List<Integer>> res, int level) {
//        if (node == null) return;
//
//        List<Integer> integers;
//        if (res.size() <= level) {
//            integers = new LinkedList<>();
//            res.add(level, integers);
//        } else integers = res.get(level);
//
//        integers.add(node.val);
//
//        level = level + 1;
//        levelTraversal(node.left, res, level);
//        levelTraversal(node.right, res, level);
//    }
//
//    public int maxDepth(TreeNode root) {
//        int[] res = new int[1];
//        maxDepth(root, res, 0);
//        return res[0];
//    }
//
//    private void maxDepth(TreeNode root, int[] res, int depth) {
//        if (root == null) {
//            return;
//        }
//
//        depth++;
//
//        res[0] = Math.max(res[0], depth);
//
//        maxDepth(root.left, res, depth);
//        maxDepth(root.right, res, depth);
//    }

//    public boolean isSymmetric(TreeNode root) {
//        if (root == null) return false;
//        return isSymmetric(root, root);
//    }
//
//    private boolean isSymmetric(TreeNode n1, TreeNode n2) {
//        if (n1 == null && n2 == null) return true;
//        if (n1 == null || n2 == null) return false;
//
//        return n1.val == n2.val
//                && isSymmetric(n1.left, n2.right)
//                && isSymmetric(n1.right, n2.left);
//    }

    // 路径总和
//    public boolean hasPathSum(TreeNode root, int targetSum) {
//        LinkedList<TreeNode> path = new LinkedList<>();
//        boolean[] res = new boolean[1];
//        hasPathSum(root, path, targetSum, res);
//        return res[0];
//    }
//
//    private void hasPathSum(TreeNode root, LinkedList<TreeNode> path, int targetSum, boolean[] res) {
//        if (root == null) return;
//
//        if (root.left == null && root.right == null) {
//            int total = 0;
//            StringBuilder sb = new StringBuilder();
//            sb.append("[");
//            for (TreeNode treeNode : path) {
//                total += treeNode.val;
//                sb.append(treeNode.val);
//                sb.append(",");
//            }
//
//            total += root.val;
//            sb.append(root.val);
//            sb.append(",");
//
//            sb.deleteCharAt(sb.length() - 1);
//            sb.append("]");
//
//
//            if (total == targetSum) {
//                sb.append("  success: path total = ");
//                sb.append(targetSum);
//                res[0] = true;
//            }
//
//            System.out.println("path = " + sb);
//        } else {
//            path.add(root);
//            hasPathSum(root.left, path, targetSum, res);
//            hasPathSum(root.right, path, targetSum, res);
//            path.remove(root);
//        }
//    }


    // 寻找最近公共祖先
//    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//        if (p == null || q == null) {
//            System.out.println("p = " + p);
//            if (p != null) System.out.println("p.val = " + p.val);
//            System.out.println("q = " + q);
//            if (q != null) System.out.println("q.val = " + q.val);
//            return p == null ? q : p;
//        }
//        System.out.println("p.val = " + p.val);
//        System.out.println("q.val = " + q.val);
//
//        LinkedList<TreeNode> pPath = new LinkedList<>();
//        LinkedList<TreeNode> qPath = new LinkedList<>();
//        pPath.add(root);
//        qPath.add(root);
//        traversal(root, p, pPath);
//        traversal(root, q, qPath);
//
//        printNode(pPath, "p path");
//        printNode(qPath, "q path");
//
//
//        LinkedList<TreeNode> parent;
//        LinkedList<TreeNode> child;
//        if (pPath.size() > qPath.size()) {
//            child = pPath;
//            parent = qPath;
//        } else {
//            child = qPath;
//            parent = pPath;
//        }
//
//        TreeNode treeNode;
//        while (!child.isEmpty()) {
//            treeNode = child.pollLast();
//            if (parent.contains(treeNode)) {
//                return treeNode;
//            }
//        }
//
//        return null;
//    }
//
//    private boolean traversal(TreeNode root, TreeNode target, LinkedList<TreeNode> path) {
//        if (root == null) return false;
//        path.addLast(root);
//        if (root == target) return true;
//        boolean leftFind = traversal(root.left, target, path);
//        boolean rightFind = traversal(root.right, target, path);
//        if (leftFind || rightFind) {
//            return true;
//        } else {
//            path.remove(root);
//            return false;
//        }
//    }


    // 寻找最近节点 - 高效
//    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//        if (root == p || root == q || root == null) return root;
//
//        TreeNode left = lowestCommonAncestor(root.left, p, q);
//        TreeNode right = lowestCommonAncestor(root.right, p, q);
//
//        if (left != null && right != null) return root;
//        if (left == null && right == null) return null;
//        return left == null ? right : left;
//    }

//    // Encodes a tree to a single string.
//    public String serialize(TreeNode root) {
//        if (root == null) return "[]";
//        StringBuilder sb = new StringBuilder();
//        sb.append("[");
//        ArrayList<LinkedList<TreeNode>> res = new ArrayList<>();
//        serializeTraversal(root, res, 0);
//
//        // 转成一维链表
//        LinkedList<Integer> linkedList = new LinkedList<>();
//        for (LinkedList<TreeNode> list : res) {
//            for (TreeNode treeNode : list) {
//                linkedList.add(treeNode != null ? treeNode.val : null);
//            }
//        }
//        // 尾部null全部移除
//        while (true) {
//            Integer integer = linkedList.peekLast();
//            if (integer == null) {
//                linkedList.pollLast();
//            } else {
//                break;
//            }
//        }
//        // 组转字符串
//        for (Integer integer : linkedList) {
//            if (integer != null) sb.append(integer);
//            else sb.append("null");
//            sb.append(",");
//        }
//
//        sb.deleteCharAt(sb.length() - 1);
//        sb.append("]");
//
//        String s = sb.toString();
//        System.out.println(s);
//        return s;
//    }
//
//    private void serializeTraversal(TreeNode node, ArrayList<LinkedList<TreeNode>> res, int depth) {
//        LinkedList<TreeNode> list;
//        if (res.size() <= depth) {
//            list = new LinkedList<>();
//            res.add(depth, list);
//        } else list = res.get(depth);
//
//        if (node == null) {
//            list.add(null);
//        } else {
//            list.add(node);
//            depth++;
//            serializeTraversal(node.left, res, depth);
//            serializeTraversal(node.right, res, depth);
//        }
//    }

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) return "[]";

        LinkedList<TreeNode> res = new LinkedList<>();

        // 广度优先，遍历Tree
        LinkedList<TreeNode> bfs = new LinkedList<>();
        bfs.add(root);
        while (!bfs.isEmpty()) {
            TreeNode treeNode = bfs.pollFirst();
            res.addLast(treeNode);

            // 空节点情况
            if (treeNode != null) {
                if (treeNode.left != null) {
                    bfs.addLast(treeNode.left);
                } else bfs.addLast(null);

                if (treeNode.right != null) {
                    bfs.addLast(treeNode.right);
                } else bfs.addLast(null);
            }
        }

        // 移除尾端null
        while (!res.isEmpty()) {
            TreeNode node = res.peekLast();
            if (node == null) {
                res.pollLast();
            } else break;
        }

        // 组装字符串结果输出
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (TreeNode node : res) {
            sb.append(node != null ? node.val : "null");
            sb.append(",");
        }
        if (sb.length() > 1) sb.deleteCharAt(sb.length() - 1);
        sb.append("]");
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        int start = data.indexOf("[");
        int end = data.indexOf("]");
        String str = data.substring(start + 1, end);
        System.out.println(str);
        if (str.isEmpty()) return null;

        String[] json = str.split(",");
        LinkedList<String> dataList = new LinkedList<>(Arrays.asList(json));
        return build(dataList);
    }

    private TreeNode build(LinkedList<String> data) {
        if (data.isEmpty()) return null;

        String str = data.pollFirst();
        if ("null".equals(str)) return null;
        TreeNode root = new TreeNode(Integer.parseInt(str));

        LinkedList<TreeNode> nextLevel = new LinkedList<>();
        nextLevel.add(root);
        while (!nextLevel.isEmpty() && !data.isEmpty()) {
            TreeNode treeNode = nextLevel.pollFirst();

            str = data.pollFirst();
            if (!"null".equals(str)) {
                treeNode.left = new TreeNode(Integer.parseInt(str));
                nextLevel.add(treeNode.left);
            }

            if (!data.isEmpty()) {
                str = data.pollFirst();
                if (!"null".equals(str)) {
                    treeNode.right = new TreeNode(Integer.parseInt(str));
                    nextLevel.add(treeNode.right);
                }
            }
        }
        return root;
    }

    Map<Integer, Integer> inorderMap = new HashMap<>();
    int[] post;

    // LC 从中序与后序遍历序列构造二叉树
    public TreeNode buildTree(int[] inorder, int[] postorder) {
//        中序遍历 inorder = [9,3,15,20,7]
//        后序遍历 postorder = [9,15,7,20,3]

        post = postorder;
        // 中序值与下标对应
        for (int i = 0; i < inorder.length; i++) inorderMap.put(inorder[i], i);

        return _buildTree(0, inorder.length - 1, 0, postorder.length - 1);
    }

    private TreeNode _buildTree(int is, int ie, int ps, int pe) {
        if (is > ie || ps > pe) return null;

        int rootVal = post[pe];
        TreeNode root = new TreeNode(rootVal);

        Integer ri = inorderMap.get(rootVal);
        if (ri == null) return null;

        root.left = _buildTree(is, ri - 1, ps, ps + ri - is - 1);
        root.right = _buildTree(ri + 1, ie, ps + ri - is, pe - 1);

        return root;
    }

    private void printNode(LinkedList<TreeNode> nodes, String prefix) {
        StringBuilder sb = new StringBuilder();
        sb.append(prefix);
        sb.append(" ");
        sb.append("[");
        for (TreeNode node : nodes) {
            sb.append(node.val);
            sb.append(",");
        }
        sb.deleteCharAt(sb.length() - 1);
        sb.append("]");
        System.out.println(sb);
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
